import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created by L.jp
 * Description:编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符
 *
 * 字符串A: abcdefg
 *
 * 字符串B: abcdef
 *
 * 通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
 *
 * 要求：
 *
 * 给定任意两个字符串，写出一个算法计算它们的编辑距离。
 * User: 86189
 * Date: 2022-03-19
 * Time: 18:33
 */
public class Main {
    //字符串编辑距离是一道经典的动态规划问题
    //问题是 ：求两个字符串的最小编辑距离，转化为子问题就是求str1的前i个字符和str2的前j个字符的最小编辑距离
    //状态定义就是：dp[i][j]  表示str1的前i个字符和str2的前j个字符的最小编辑距离
    //同样这个问题可以转化为二维数组来求解，求编辑距离就是str1最少可以经过多少步变为str2,也就是最后两个字符串是匹配的
    //对于这个问题有两种情况：
    //   1.当str1[i]==str2[j]时，要想str1变为str2，我们就不用管第i个字符和第j个字符，直接比较前面的i-1和j-1个字符，也就是dp[i][j]=dp[i-1][j-1]
    //   2.当str1[i]!=str2[j]时，就可以有三种操作变换：
//           1.插入操作：如果我们可以在str[i]的后面加上一个str2[j]，使得两个字符串匹配，那么就说明前i个字符和前j-1个字符是匹配的，既然str1[i+1]和str2[j]相等了，就相当于可以抵消，
//             则就可以转化为第一种情况，把下标换一下就行，即dp[i][j]=dp[i][j-1]+1,  这个+1就是我们的插入操作
//           2.删除操作：如果我们采取删除操作，在str1上删除一个字符使得变得和str2匹配，那么也就是说str1的前i-1个字符是和str2的前j个字符是一样的，所以dp[i][j]=dp[i-1][j]+1
//              这个+1操作就是在str1的基础上的删除操作
//           3.替换操作：如果我们采取替换操作使得str1的前i个字符和str2的前j个字符匹配，那么说明前i-1个字符和前j-1个字符是匹配的，所以dp[i][j]=dp[i-1][j-1]+1,这个+1就是替换操作
    public static  int editDistance(String str1,String str2){
        char[] s1=str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int len1=s1.length;
        int len2 = s2.length;
        int[][] dp=new int[len1+1][len2+1];
        //需要借助初始状态，表示空串变为空串的编辑距离就是0，因为数组初始化就是0，所以可以不用管
        //还有两个初始状态就是空串依次变为str2，那么就是插入操作，编辑距离就是字符的位置
        //还有一个初始状态就是str1串依次变为空串，那么就是删除操作，编辑距离也是字符位置

        //接下来构造dp数组
        //第一列
        for(int i = 0; i <= len1; i++){
            dp[i][0]=i;
        }
        //第一行
        for(int j = 0; j <= len2; j++){
            dp[0][j]=j;
        }
        //构造中间部分
        for(int i =1;i<=len1;i++){
            for(int j = 1; j <=len2; j++){
                //在字符数组中下标和字符串中字符的位置需要-1
                if(s1[i-1]==s2[j-1]){
                    dp[i][j] =dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[len1][len2];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String str1;
        while ((str1 = bf.readLine())!=null){
            String str2=bf.readLine();
            System.out.println(editDistance(str1, str2));

        }


    }
}
